/**
 *
 * @param {Array} arr
 * @returns {number}
 */
function bubleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
}

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 找到未排序部分的最小值的索引
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    // 将找到的最小值与i位置的值交换
    if (minIndex !== i) {
      [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
    }
  }
}

function quickSort1(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  const pivot = arr[right]; // 选择最右侧的元素作为基准
  let i = left - 1; // i是小于基准元素的最后一个位置

  for (let j = left; j < right; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // 交换元素
    }
  }

  [arr[i + 1], arr[right]] = [arr[right], arr[i + 1]]; // 把基准元素放到正确的位置
  return i + 1;
}
/**
 * 快速排序函数
 * @param {Array} arr - 待排序的数组
 * @param {number} start - 排序起始索引，默认为0
 * @param {number} end - 排序结束索引，默认为数组长度减1
 */
function quickSort(arr, start = 0, end = arr.length - 1) {
  // 当起始索引大于等于结束索引时，无需排序，直接返回
  if (start >= end) return;
  let left = start;
  let right = end;
  // 选择中点作为基准值
  pivot = arr[(left + right) >>> 1];
  // 当左指针小于等于右指针时，进行循环
  while (left <= right) {
    // 当左指针位置的元素小于基准值时，左指针右移
    while (arr[left] < pivot && left <= right) left++;
    // 当右指针位置的元素大于基准值时，右指针左移
    while (arr[right] > pivot && left <= right) right--;
    // 当左指针小于等于右指针时，交换左右指针位置的元素，并更新指针位置
    if (left <= right) {
      [arr[left], arr[right]] = [arr[right], arr[left]];
      left++;
      right--;
    }
  }
  // 递归调用快速排序，对左子数组进行排序
  quickSort(arr, start, right);
  // 递归调用快速排序，对右子数组进行排序
  quickSort(arr, left, end);
}

const arrMin = [5, 3, 8, 4, 2, 1, 3, 7];
var arr = new Array(50000).fill(Math.ceil(Math.random() * 10));
const start = Date.now();
// quickSort(arrMin);
selectionSort(arrMin);
// quickSort(arr);
// quickSort1(arr);
// bubleSort(arr);
selectionSort(arr);
// arr.sort((a, b) => b - a);
console.log(arrMin, Date.now() - start + "ms");
